package com.exam.exercise;

/**
 * @Author: xin.wang  E-mail:xin.wang1@myt11.com
 * @CreateTime: 2022/2/11 10:06
 * @Description: 最小覆盖子串
 */
public class FristExercise {
    /**
     * 给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串
     *
     * 示例1
     * 输入："XDOYEZODEYXNZ","XYZ"
     * 返回值："YXNZ"
     * 示例2
     * 输入："abcAbA","AA"
     * 返回值："AbA"
     *
     * @param args
     */
    public static void main(String[] args) {
        String s = "XDOYEZODEYXNZ";
        String t = "XYZ";
        System.out.println(MinimumCoverSubstring(s,t));
    }

    public static String MinimumCoverSubstring(String s, String t) {
        int[] arr = new int[123];
        int t_string = 0;
        for (int i = 0; i < t.length(); i++) {
            if (arr[t.charAt(i)] == 0) {
                t_string++;
                arr[t.charAt(i)]++;
            } else {
                arr[t.charAt(i)]++;
            }
        }
        int left = 0;
        int right = 0;
        int len = s.length();
        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i)]--;
            if (arr[s.charAt(i)] == 0) {
                t_string--;
            }
            if (t_string == 0) {
                while (arr[s.charAt(right)] < 0) {
                    arr[s.charAt(right)]++;
                    right++;
                }

                if (len - left > i - right) {
                    len = i;
                    left = right;
                }
            }
        }
        return s.substring(left, len + 1);
    }

}
